#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "LinkTree.h"
#include "DoubleLinkList.h"
//1：写一个算法将单链表就地逆置，要求使用递归
// 定义单链表节点结构
struct ListNode {
    int data;
    struct ListNode* next;
};

// 递归函数，将链表就地逆置
struct ListNode* reverseList(struct ListNode* head) {
    // 链表为空或只有一个节点，无需反转
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 递归反转链表的剩余部分
    struct ListNode* newHead = reverseList(head->next);

    // 将当前节点的下一个节点的指针指向当前节点，实现反转
    head->next->next = head;
    head->next = NULL;

    // 返回新的头节点
    return newHead;
}

//2通用树的添加节点，删除节点
// 添加一个子节点到通用树
void addChild(struct TreeNode* parent, int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;
   return newNode;

    // 如果父节点没有子节点，直接将新节点设置为第一个子节点
    if (parent->firstChild == NULL) {
        parent->firstChild = newNode;
    } else {
        // 否则，遍历兄弟节点链表，将新节点添加到兄弟节点链表的末尾
        struct TreeNode* current = parent->firstChild;
        while (current->nextSibling != NULL) {
            current = current->nextSibling;
        }
        current->nextSibling = newNode;
    }
}


//删除节点：
void deleteSubtree(struct TreeNode* root) {
    if (root == NULL)
 {
        return NULL;
    }

    // 递归删除所有子节点
    struct TreeNode* current = root->firstChild;
    while (current != NULL) {
        struct TreeNode* temp = current;
        current = current->nextSibling;
        deleteSubtree(temp);
    }

    // 释放当前节点的内存
    free(root);
}


//3、平衡二叉树的插入函数
TNode *InsertNode (TNode *root,int value)
{   
    if(root==NULL)
    {
        root=CreateNode(value);
    }
    else if(root->value > value) 
    {
        //插入的一定是左子树
        root ->left = InsertNode(root->left,value);
        //左子树高度一定比右子树高
        if(GetNodeHeight(root->left) - GetNodeHeight(root->right)>1)
        {
            
            printf("失衡了，进行旋转恢复平衡!\n");
            //判断比左孩子大还是小，判断是左左插入还是左右插入
            root=root ->left->value >value? RotateRight(root): RotateLeftRight(root);
        }
    }
    else 
    {
        root -> right=InsertNode(root->right ,value) ;
        if(GetNodeHeight (root->left)-GetNodeHeight (root->right) < -1)
        {
            root =root ->right ->value <value ? RotateLeft(root):RotateRightLeft(root);            
        }       
    }
    return root;
}

//4、求二叉树的最大深度
int GetTreeNodeHeight(LTNode *node)

{
    if(node==NULL)
    return 0;
    //当前已经获得的高度
    int height=0;
    LTNode *TravelNode=node->firstChild;
    while(TravelNode!=NULL)
    {
        //递归计算孩子的高度
        int childHeight=GetTreeNodeHeight(TravelNode);
        height=height>childHeight?height:childHeight;
        TravelNode=TravelNode->nextSbling;
    }
    return height+1;
}

int GetTreeHeight(LTree *tree)
{
    return GetTreeNodeHeight(tree->root);
}
//5.线性表中的元素递增有序按照顺序存储在计算机内，
// 要求设计一个算法用最少时间在表中查找为x的元素，若找到，将其与后继元素位置交换，
// 若找不到，则将其插入有序表使表中元素任然式有序表

struct ListNode* findAndModify(struct ListNode* head, int target) {
    if (!head) {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = target;
        newNode->next = NULL;
        return newNode;
    }

    struct ListNode* prev = NULL;
    struct ListNode* current = head;

    while (current && current->val < target) {
        prev = current;
        current = current->next;
    }

    if (current && current->val == target) {
        // 找到元素，交换位置
        if (current->next) {
            int temp = current->val;
            current->val = current->next->val;
            current->next->val = temp;
        }
    } else {
        // 未找到元素，插入保持有序
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = target;

        if (!prev) {
            newNode->next = head;
            head = newNode;
        } else {
            newNode->next = prev->next;
            prev->next = newNode;
        }
    }

    return head;
}







//6.双链表的排序（不允许交换节点里面的值，通过改变指针的指向实现）
// 插入排序
void insertionSort(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;  // 如果链表为空或只有一个节点，无需排序
    }

    // 初始化已排序部分的头节点和当前待排序节点
    struct ListNode* sorted = head->next;  // 已排序部分的头节点
    struct ListNode* current = sorted->next;  // 当前待排序节点

    while (current != NULL) {
        // 找到插入位置
        struct ListNode* insertPos = sorted;  // 从已排序部分的头节点开始
        while (insertPos->prev != NULL && insertPos->value > current->value) {
            insertPos = insertPos->prev;  // 逐个向前找到合适的插入位置
        }

        // 将当前节点插入到找到的位置
        if (insertPos->prev != NULL) {
            insertPos->prev->next = current;  // 更新前一个节点的next指针
        }
        current->prev = insertPos->prev;  // 设置当前节点的prev指针
        insertPos->prev = current;  // 更新插入位置的prev指针
        current = current->next;  // 处理下一个待排序节点
        insertPos->prev->next = insertPos;  // 更新插入位置的next指针
    }
}









//7.有两个递增的链表Link_A,Link_B，设计一个算法，求链表Link_A 和链表Link_B的交集，将其结果存在Link_A中（增删改查接口可省略，关键接口需要实现）


struct ListNode* mergeIntersectedList(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;  // 哑节点，简化链表操作
    struct ListNode* tail = &dummy; // 指向当前合并链表的尾部

    while (l1 && l2) {
        if (l1->val == l2->val) {
            tail->next = l1;
            tail = tail->next;
            l1 = l1->next;
            l2 = l2->next;
        } else if (l1->val < l2->val) {
            l1 = l1->next;
        } else {
            l2 = l2->next;
        }
    }

    tail->next = NULL;  // 断开合并链表的末尾
    return dummy.next;  // 返回合并后链表的头部
}








//8.设A和B是两个单链表，其中元素递增有序。将AB两个链表合并成一个新的有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;  // 哑节点，简化链表操作
    struct ListNode* tail = &dummy; // 指向当前合并链表的尾部

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 如果其中一个链表还有剩余元素，直接将剩余部分接到合并链表的尾部
    if (l1) {
        tail->next = l1;
    }
    if (l2) {
        tail->next = l2;
    }

    return dummy.next;  // 返回合并后链表的头部
}







//9.给定一个未经排序的整数数组，找到最长连续递增子序列的长度。

int findLengthOfLCIS(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }

    int max_length = 1;  // 最小长度为1，因为至少有一个元素
    int current_length = 1;

    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] > nums[i - 1]) {
            current_length++;
            if (current_length > max_length) {
                max_length = current_length;
            }
        } else {
            current_length = 1;
        }
    }

    return max_length;
}



//10.给定一个链表，判断链表中是否有环。若有环，找出环的入口节点。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    bool has_cycle = false;

    // 判断是否有环
    while (fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            has_cycle = true;
            break;
        }
    }

    if (!has_cycle) 
    {

        return NULL;  // 没有环
    }

    // 找到环的入口节点
    slow = head;
    while (slow != fast) 
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

//11动态排序
bool WordBreak(char *s,char **wordDIct,int wordDictSize)
{
    int i;int k;int j;
    int len =strlen(s);
    int dp[len+1];
    memset[dp,0,len+1];//初始化
    dp[0]=1;//将dp数组的第一位置1，其余位置为0；
    for(int i=1;i<=len;i++)//遍历字符串
    {
        for(int j=0;j<wordDictSize;j++)//遍历词典的每个的单词
        {
            k=i-strlen(wordDict[j])
                if(k<0)
                    continue;
            dp[i]=dp[k]&&!strncmp(s+k,wordDict[j],strlen(wordDict[j]))
                if(dp[i]==1)
                    break;
        }
    }
    return dp[len];
}











